package com.since.data_structure.linkedlist;

/**
 * Created by Sincerity on 2020/5/6.
 * 描述：单链表数据结构
 */
public class SingleLinkedList {
    //头结点
    private Entry head = new Entry(0, "", "");

    /**
     * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转
     *
     * @param head
     * @param m
     * @param n
     */
    public void reverseBetween(Entry head, int m, int n) {
        Entry temp = head;
        Entry next;
        for (int i = 1; i < m; i++) {
            temp = temp.next;
        }
        //temp =前一个节点 3
        //得到需要变化的下一个节点4
        head = temp.next;
        for (int i = m; i < n; i++) {
            next = head.next; // 后一个节点5
            head.next = next.next;//null
            next.next = temp.next;//4
            temp.next = next;//
        }
        showList();

    }

    /**
     * 没有头结点参与运算的反转
     *
     * @param head 首节点
     */
    void reverseLinkedListNoHead(Entry head) {
        //保存当前节点这个节点的位置是相对的, 其实当前节点数据是一直没有变化的 固定是原链表首节点
        // 只是头部一直插入节点导致这个值一直在后移
        //元链表首节点的下一个节点
        Entry reverseNode;
        Entry realHead = head;
        //保存一个原地移动后的首节点
        while (head.next != null) {
            reverseNode = head.next;
            head.next = reverseNode.next;
            reverseNode.next = realHead;
            realHead = reverseNode;
        }
        this.head = realHead;
        showList();
    }

    /**
     * 链表的原地反转算法
     *
     * @param head 链表的头结点
     */
    void reverseLinkedList2(Entry head) {
        //保存当前节点这个节点的位置是相对的, 其实当前节点数据是一直没有变化的 固定是原链表首节点
        // 只是头部一直插入节点导致这个值一直在后移
        Entry current = head.next;
        //元链表首节点的下一个节点
        Entry next;
        //保存一个原地移动后的首节点
        Entry temp;
        while (current.next != null) {
            //得到原链表的下一个节点
            next = current.next;
            //这个代码表示把next节点在原链表位置删除
            current.next = next.next;
            //保存当前位置的头结点
            temp = head.next;
            //把next节点插入头节点
            head.next = next;
            //把next的尾结点指向原来的头结点
            next.next = temp;
        }
        showList();
    }

    /**
     * 链表的反转 (头节点插入法)
     * 需要二个辅助变量 1. 当前节点 2. 当前节点的下一个节点
     * 原因就是得到当前节点后,当前节点的next指针会指向新链表导致和原链表失去关系,
     * 靠提前保存的下一个节点重新与原链表建立关系
     *
     * @param head 头节点
     */
    private void reverseLinkedList(Entry head) {
        //1.思路 新建一个链表 2.遍历旧链表 每遍历一个节点 3.就把这个节点插入到新链表的第一个位置
        Entry newEntry = new Entry(0, "", "");
        Entry temp = head.next;
        Entry next;
        while (temp != null) {
            //最好画个图自己详细理解一下
            //得到临时指针节点的下一个节点 ,为什么要得到临时指针的下一个节点
            // 因为下面会把这个临时指针和临时指针的next节点改变指向
            next = temp.next;
            //临时指针的一个节点变成新链表的头节点
            temp.next = newEntry.next;
            //让这个节点断掉和head节点的指针 从而把新链表的下一个位置指向这个临时节点 变成一个新的链表
            newEntry.next = temp;
            //因为在上一步已经断掉了temp和head的指向关系 所以这时候将前面保存的next值重新付给temp 让temp和head重新关联
            temp = next;
        }
        //为了保证是同一个链表 将指针重新指向新链表的第一个节点
        head.next = newEntry.next;
    }

    /**
     * 得到链表的倒数第n个节点
     *
     * @param head 头结点
     * @return 返回倒数的第n个节点
     */
    Entry getLastIndexForNode(Entry head, int index) {
        int effectiveNodeNum = getEffectiveNode(head);
        if (index <= 0 || index > effectiveNodeNum) {
            return null;
        }
        Entry temp = head.next;
        int length = 0;
        while (temp != null) {
            //这个算法的理解就在于 倒数index节点=链表的长度-倒数index的索引
            //eg 倒数第5 长度12 我们应该找的节点 就是 12-5 的正数第7个节点
            if (length++ == effectiveNodeNum - index) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * 得到链表的有效节点个数
     *
     * @param head 链表的头结点
     * @return 返回有效节点的个数
     */
    int getEffectiveNode(Entry head) {
        int length = 0;
        if (head.next == null) return length;
        while (head.next != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    /**
     * 得到头结点
     *
     * @return 头结点
     */
    public Entry getHeader() {
        return head;
    }

    /**
     * 向链表添加数据
     *
     * @param entry 需要添加的新节点
     */
    void addEntry(Entry entry) {
        Entry temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = entry;
    }

    /**
     * 按照节点的大小顺序去添加节点
     *
     * @param entry 需要添加的新节点
     */
    public void addEntryForOrderById(Entry entry) {
        Entry temp = head;
        boolean flag = false;
        while (temp != null) {
            if (temp.next.no > entry.no) {
                break;//扎到新节点的位置
            } else if (temp.next.no == entry.no) {
                flag = true; // 存在一个相同的id的节点
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", entry.no);
        } else {
            entry.next = temp.next;
            temp.next = entry;
        }
    }

    /**
     * 通过节点的编号删除节点
     *
     * @param no 需要删除的编号 {@link #addEntry(Entry)}
     */
    void deleteEntry(int no) {
        Entry temp = head;
        boolean flag = false;
        while (temp.next != null) {
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("需要删除的节点不存在");
        }
    }

    /**
     * 修改链表的节点信息 这里是以链表的编号为主键的,
     * 如果二个节点的编号不一样
     * 则表示需要2添加一个新节点{@link #addEntry(Entry)}而不是修改节点
     *
     * @param entry 需要修改的节点
     */
    public void updateEntry(Entry entry) {
        Entry temp = head;
        boolean flag = false;
        while (temp.next != null) {
            if (temp.no == entry.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = entry.name;
            temp.nikeName = entry.nikeName;
        } else {
            System.out.printf("没有找到 编号 %d 的节点，不能修改\n", entry.no);
        }
    }

    public void showList() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Entry temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class Entry {
    int no;
    String name;
    String nikeName;
    Entry next;

    public Entry(int no, String name, String nikeName) {
        this.no = no;
        this.name = name;
        this.nikeName = nikeName;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nikeName='" + nikeName + '\''
                + '}';
    }
}